Computer networks continue to proliferate. As a result, data traffic among networks continues to rise, placing ever-increasing demands on the ability of network structures to transfer data between source and destination locations. Network data is usually transferred in data units referred to as "packets" (or datagrams) that are transmitted from a source machine and eventually received by a destination machine. While network data transfers may appear transparent to both the source machine and the destination machine, in actuality, the data packets are usually transferred between intermediate stages (referred to as "hops") by machines referred to as "routers." A router will receive a packet, examine destination information within the packet, and from this destination information, "forward" the packet to a "next" hop destination. In this manner, data is forwarded by one or more hops, and eventually arrives at the desired destination. The function of examining a destination address and determining next hop information is often referred to as "address matching."
Routing functions rely on an underlying standardization in the data packet format and transmission method (protocols). One of the most prevalent protocols is the internet protocol (IP). IP serves to route a given packet from a source to a destination. To accomplish this function an IP data packet will include an initial portion (header) that includes, among other information fields, a source address and a destination address. As noted above, it is the destination address that is utilized by a routing machine to transfer a data packet to its next hop or final destination. To accomplish the routing function, a router will typically include a "look-up" table that includes next hop information corresponding to particular destination addresses. The router examines the destination address of an incoming packet, looks up the next hop information, and uses the next hop information to forward the packet onward toward its destination.
Routing functions can be performed by general purpose processors with conventional memory devices that run a routing algorithm. Such an approach can result in limited throughput of data packets, be expensive in terms of component cost, and require considerable area to implement.
An alternate way to address the need for faster routers is to fabricate an integrated circuit that is specialized to perform routing tasks. Such application specific integrated circuits (ASICs), because they are custom manufactured products, can also be expensive to manufacture and implement.
One type of device that is particularly suitable for router address matching functions is a content addressable memory (CAM), also referred to as an "associative memory." A CAM includes a number of data storage locations, each of which can be accessed by a corresponding address. The order in which the data values are stored varies according to the type of CAM. As just one example, in a typical "binary" CAM, data can be stored in the first available "empty" location. Empty locations are distinguished from "full" (or valid) locations by a status bit associated with each storage location.
Once data is stored in a CAM, valid locations can then be addressed according to the contents (data values) that they store. A comparand value is loaded into a comparand register. The value within the comparand register can then be compared to the data values within each valid location. In the event the value within the comparand register matches the value of a storage location, a match signal for the matching storage location will be generated. In the event there is more than one match, one match from the multiple matches will be selected according to predetermined priority criteria. The address corresponding to the match location can then be made available.
Among the various types of CAMs are binary CAMs and ternary CAMs. A binary CAM typically includes a number of CAM cells arranged into rows and columns, with CAM cells of the same row being commonly coupled to a word line, and CAM cells of the same column being commonly coupled to the same bit line (or bit line pair). Each binary CAM cell includes a storage circuit, for storing a data value, and a compare circuit for comparing the stored data value to a comparand value. When the comparand value matches the data value, the binary CAM cell will provide a bit match indication.
As noted above, a binary CAM can provide a rapid look-up function for an IP address. However, this is only true when the look-up function is for IP addresses having the same number of bits. Unfortunately, IP addresses can have prefixes of variable length. To illustrate this point, an example of two variable length prefix addresses is set forth below. The prefix values that must be matched are shown as binary values (either 0 or 1). The remaining portions of the IP address that do not have to be matched, are represented by a series of Xs. EQU 11110000 10XXXXX XXXXXXXX XXXXXXXX (address 1) EQU 10101010 01010101 100XXXXX XXXXXXXX (address 2)
Thus, the first address requires a router to find a match with a 10-bit prefix, while the second address requires a match with a 19-bit prefix. For proper routing of data packets, it is desirable for a router to perform a longest prefix matching function to ensure that the proper next hop information is associated with a data packet.
A prior art way to address longest prefix matching is to utilize a "ternary" or "tertiary" CAM. In a ternary CAM, a data value is stored according to the length of its prefix. This is accomplished by providing a prefix (or inverse mask) bit for each bit of data. An example of a ternary CAM storage arrangement is illustrated by a table set forth in FIG. 1. The table of FIG. 1 describes a ternary CAM having eight locations, each of which can store a data word having a length of four bits. Longest prefix matching is required, thus the ternary CAM is required to compare either all four bits, the first three bits, the first two bits or the first bit of the data words. To indicate which bits comprise a prefix, the ternary CAM includes prefix data corresponding to each bit storage location. If reference is made to FIG. 1, it is shown that data location "0" stores the four-bit data value A3 A2 A1 A0. Corresponding to the data location 0 is the prefix value 1111. This prefix value indicates that all four bits are to be compared with a comparand value. In contrast, data location "5," which stores the four-bit data value F3 F2 F1 F0, has a prefix value of 1100. This prefix value indicates that the first two bits F3 and F2 are to be compared with a comparand value.
A prior art ternary CAM cell is set forth in FIG. 2 and designated by the general reference character 200. The ternary CAM cell 200 includes some of the same circuit constituents as the binary CAM cell described above. Namely, the ternary CAM cell 200 includes a data register 202 and a compare circuit 204. As in the case of the binary CAM cell, the data register 202 serves to store data value and the compare circuit 204 serves to compare the stored data value to an applied comparand value (C and /C). The data register 202 is coupled to a complementary bit line pair (B and /B) by a value word line (VWL). The compare circuit 204 receives the data value stored by the data register 202 and the comparand value (C and /C), and compares the two values to generate a pre-match value (PMATCH).
To accomplish the variable prefix matching function, the ternary CAM cell 200 further includes a mask register 206 and a mask circuit 208. The mask register 206 stores the mask (inverse prefix) value that corresponds to the data value in the data register 202. For example, referring back to FIG. 1, the prefix value corresponding to the G3 value stored in location 6 is "1." The prefix value is the inverse of the mask value, thus, if the data register 202 stores the G3 value, the mask register 206 would store a "0" value (i.e., the entire mask value for the data word at storage location 6 would be 0111, the inverse of the prefix value shown in the table of FIG. 1).
In the prior art arrangement of FIG. 2, the mask register 206 has the same general structure as the data register 202, and a mask value can be written into the mask register 206 by way of the bit line pair (B and /B) by activating a corresponding mask word line MWL. The value stored by the mask register 206 is supplied to the mask circuit 208. The mask circuit 208 provides a match value MATCH having a value that will depend upon the mask value MASK. In the event the MASK value is low (indicating that the stored data bit is a prefix bit--and the results of the compare operation are desired), the PMATCH value is provided as an output by the mask circuit 208 to generate the MATCH value. Conversely, when the MASK value is high (indicating that the stored data bit is not part of the prefix--and the results of the compare operation are to be ignored) the PMATCH value is prevented from being passed through the mask circuit 208.
Referring now to FIG. 3, a prior art register that may be used as the storage register 202 or the mask register 206 is set forth in a block schematic diagram. The register is designated by the general reference character 300 and includes a pair of cross-coupled inverters I300 and I302. The inverters (I300 and I302) are "cross-coupled" in that the output of inverter I300 is coupled to the input of inverter I302, and vice versa. The outputs of the inverters (I300 and I302) provide the data values on lines D and /D. Thus, the node formed at the output of inverter I302 and the input of inverter I300 can be considered a data node. The inverters (I300 and I302) provide the storage function of the register 300, and are accessed by two n-channel pass transistors N300 and N302. Transistor N300 has a source-drain path coupled between bit line B and the input of inverter I300. Transistor N302 has a source-drain path coupled between bit line /B and the input of inverter I302. T he gat es of transistors N300 and N302 are commonly coupled to a word line WL. In the case of a storage register, the word line would be a value word line (VWL). In the case of a mask register, the word line would be a mask word line (MWL).
FIG. 4 sets forth a prior art compare circuit 400 that may be used as the compare circuit 204 set forth in FIG. 2. The compare circuit is an exclusive OR (XOR) circuit that includes a first pair of n-channel transistors N400 and N402 arranged in series between a match node 402 and a ground voltage GND. The gate of transistor N400 receives a comparand value C. The gate of transistor N402 receives the complementary data value /D. The compare circuit 400 further includes a second pair of transistors N404 and N406 arranged in series between the match node 402 and the GND voltage. The gate of transistor N404 receives a complementary comparand value /C and the gate of transistor N406 receives a data value D. In the event the comparand values (C and /C) are different than the data values (D and /D, respectively), the match node 402 will be discharged to the GND voltage. However, in the event the comparand values (C and /C) are different than the data values (D and /D), the match node 402 will remain at a precharged level, indicating a bit match condition.
Finally, FIG. 5 is a schematic diagram illustrating a mask circuit that may be used as the mask circuit 208 set forth in FIG. 2. The mask circuit 500 is shown to be a p-channel metal-oxide-semiconductor (MOS) transistor P500 having a source-drain path coupled between the PMATCH signal and the MATCH signal. The gate of transistor P500 is driven by the MASK signal. In this arrangement, if the MASK signal is low, the PMATCH signal is provided as the MATCH signal. If the MASK signal is high, transistor P500 is turned off, preventing the PMATCH signal from being transmitted, and thereby "masking" the bit compare operation result.
While the ternary CAM 200 provides for parallel, variable prefix matching, it requires that the data values be loaded into the storage locations in a particular order. As shown in FIG. 1, those data values having the longest prefixes must precede those with shorter prefixes. In this arrangement, as a comparand value is applied, it is first matched against location 0, then location 1, and so on, until all locations have been examined. The priority of the match will be established by the location of the match. Thus, if an applied comparand value generates a match indication for location 1 (i.e., the first four bits of the comparand value match B3 B2 B1 and B0) and generates a match indication for location 3 (i.e., the first three bits of the comparand value match D3 D2 an D1), location 1, due to its location number, will provide the largest prefix match.
The above discussion has assumed that the ternary CAM values remain static. In most applications this is not the case. Routers, for example, consistently update next hop information. This can present a problem to the conventional ternary CAM as it requires that stored data values to be re-ordered when a new data value is added, or an old data value is removed. A conventional update (i.e., re-order) operation for a ternary CAM can be illustrated by referring once again to FIG. 1. If it is assumed that a new data value must be added (Z3 Z2 Z1 Z0), and the value has prefix data equal to "1110," data location 3 must be freed, and those values having a prefix length equal to or less than the new data value will have to be rewritten into a higher number location. That is, data value H3 H2 H1 H0 will have to written into data location 8, G3 G2 G1 G0 will have to written into data location 7, F3 F2 F1 F0 will have to written into data location 6, E3 E2 E1 E0 will have to written into data location 5, and D3 D2 D1 D0 will have to written into data location 4. Data location 3 would then be free, and the Z3 Z2 Z1 Z0 value could be written into that location. It is clear that adding a data value to ternary CAM requires a considerable amount of time, particularly if there are many data values in the ternary CAM.
The deletion of a data value from a conventional ternary CAM can also be time consuming. This aspect can be illustrated once again by referring to FIG. 1. If it is assumed that the data value at data location 1 (B3 B2 B1 B0) is to removed, data location 1 would be overwritten with the C3 C2 C1 C0 value, data location 2 would then be overwritten with the D3 D2 D1 D0 value, data location 3 would be overwritten with the E3 E2 E1 E0 value, and so on, until data location 6 is overwritten with the H3 H2 H1 H0 value. The various read and write functions required to reorder data values in a conventional ternary CAM is typically accomplished by software within the router.
Major routers may need to be updated as much as several hundred times a second. Thus, when CAMs are utilized for the look-up function, a substantial amount of time must be dedicated to simply updating the CAM values. The problem is compounded by the fact that the routing function is a "real-time" process, in which packets can arrive at any time. If the CAM values must be updated, the forwarding function of the router must be temporarily suspended to allow for the update operation (addition or removal of data values) to take place. This often requires the addition of devices that provide a relatively deep buffering function. In this way, routers that utilize ternary CAMs can suffer in performance and incur additional expense due to the update requirements.
It would be desirable to provide some way reducing the time required to add or delete a data value stored in a ternary CAM and yet maintain a predetermined order within the CAM.